public class Main {
    //直接插入排序
    public static void insertSort(int[] array){
        for (int i=1;i< array.length;i++){
            int tmp = array[i];
            int j = i-1;
            for (;j>=0;j--){
                if (array[j] > tmp){
                    //大于就往后挪一个位置
                    array[j+1] = array[j];
                }else {
                    //不大于就直接结束这次内循环
                    //因为前面的值都是已经排序好的
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    //希尔排序
    //缩小增量排序
    public static void shellSort(int[] array){
        int gap = array.length;
        while (gap > 1){
            gap /= 2;
            shell(array,gap);
        }
    }

    private static void shell(int[] array, int gap) {
        for (int i=gap;i<array.length;i++){
            int tmp = array[i];
            int j = i-gap;
            for (;j>=0;j-=gap){
                if (array[j] > tmp){
                    array[j+gap] = array[j];
                }else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }

    //直接选择排序
    public static void selectSort(int[] array){
        for (int i=0;i<array.length;i++){
            int minIndex = i;
            for (int j = i+1; j <array.length ; j++) {
                //比当前的最小值要小,就将最小值的下标替换掉
                if (array[j] < array[minIndex]){
                    minIndex = j;
                }
            }
            if (i!=minIndex){
                int tmp = array[i];
                array[i] = array[minIndex];
                array[minIndex] = tmp;
            }
        }
    }

    //堆排序
    //排升序要建立大根堆
    public static void heapSort(int[] array){
        //先建立大根堆
        createBigHeap(array);
        int end = array.length-1;
        while (end > 0){
            //交换堆顶元素和末尾元素
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }

    //建立大根堆
    //从最后一颗子树的根节点开始,每一次都进行向下调整
    private static void createBigHeap(int[] array) {
        for (int i=(array.length-1-1)/2;i>=0;i--){
            shiftDown(array,i, array.length);
        }
    }

    //向下调整
    private static void shiftDown(int[] array,int parent,int len){
        int child = (2*parent)+1;
        while (child < len){
            if (child+1 < len && array[child+1] > array[child]){
                child = child + 1;
            }
            if (array[child] > array[parent]){
                swap(array,child,parent);
                parent = child;
                child = (2*parent)+1;
            }else {
                break;
            }
        }
    }
    public static void swap(int[] array,int x,int y){
        int tmp = array[x];
        array[x] = array[y];
        array[y] = tmp;
    }

    //冒泡排序
    //相邻元素之间的比较
    public static void bubbleSort(int[] array){
        for (int i=0;i<array.length-1;i++){
            for (int j=0;j<array.length-1-i;j++){
                if (array[j] > array[j+1]){
                    swap(array,j,j+1);
                }
            }
        }
    }

    //快速排序
    public static void quickSort(int[] array){
        quick(array,0,array.length-1);
    }

    private static void quick(int[] array, int start, int end) {
        if (start >= end){
            return;
        }
        int pivot = partition(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }

    private static int partition(int[] array, int left, int right) {
        int i = left;
        int pivot = array[left];
        while (left < right){
            while (left < right && array[right] >= pivot){
                right--;
            }
            //代码走到这里right下标的值小于pivot
            while (left < right && array[left] <= pivot){
                left++;
            }
            //代码走到这里left下标的值大于pivot
            swap(array,left,right);
        }
        swap(array,i,left);
        return left;
    }

    //归并排序
    public static void mergeSort(int[] array){
        mergeSortChild(array,0,array.length-1);
    }

    private static void mergeSortChild(int[] array, int left, int right) {
        if (left == right){
            return;
        }
        int mid = (left+right)/2;
        mergeSortChild(array,left,mid);
        mergeSortChild(array,mid+1,right);
        merge(array,left,mid,right);
    }

    private static void merge(int[] array, int left, int mid, int right) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;
        int[] tmpArr = new int[right-left+1];
        int k = 0;
        while (s1<=e1 && s2<=e2){
            if (array[s1] <= array[s2]){
                tmpArr[k++] = array[s1++];
            }else {
                tmpArr[k++] = array[s2++];
            }
        }
        while (s1 <= e1){
            tmpArr[k++] = array[s1++];
        }
        while (s2 <= e2){
            tmpArr[k++] = array[s2++];
        }
        for (int i = 0; i < tmpArr.length; i++) {
            array[i+left] = tmpArr[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{5,8,1,3,9,6,7,0};
        //insertSort(arr);
        //shellSort(arr);
        //selectSort(arr);
        //heapSort(arr);
        //quickSort(arr);
        mergeSort(arr);
        for (int x: arr) {
            System.out.print(x+" ");
        }
    }


}
